package Tree.binTree.Test;

import java.util.LinkedList;
import java.util.Queue;

public class BinaryTree {


    public static class BTNode{
        BTNode left;
        BTNode right;
        int data;

        public BTNode(int data){
            this.data = data;
        }
    }
    public BTNode root = null;
    public void createBinaryTree(){
        BTNode node1 = new BTNode(1);
        BTNode node2 = new BTNode(2);
        BTNode node3 = new BTNode(3);
        BTNode node4 = new BTNode(4);
        BTNode node5 = new BTNode(5);
        BTNode node6 = new BTNode(6);

        root = node1;
        node1.left = node2;
        node2.left = node3;
        node1.right = node4;
        node4.left = node5;
        node5.right = node6;
    }

    /**
     * 前序遍历
     * 根 - 左 - 右
     */
    public void preOrder(BTNode node){
        if(node == null){
            System.out.print("null ");
            return;
        }
        System.out.print(node.data + " ");
        preOrder(node.left);
        preOrder(node.right);
    }

    /**
     * 中序遍历
     * 左 - 根 - 右
     * @param root
     */
    public void inOrder(BTNode root) {
        if(root == null){
            System.out.print("null ");
            return;
        }
        inOrder(root.left);
        System.out.print(root.data + " ");
        inOrder(root.right);
    }

    /**
     * 后序遍历
     * 左 - 右 - 根
     * @param root
     */
    public void postOrder(BTNode root) {
        if(root == null){
            System.out.print("null ");
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.data + " ");
    }
    /**
     * 层序遍历
     */
    public void levelOrder(BTNode root) {
        Queue<BTNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            BTNode node =  queue.poll();
            if(node != null){
                System.out.print(node.data + " ");
                queue.add(node.left);
                queue.add(node.right);
            }
        }
    }

    /**
     * 计算二叉树的结点个数
     * 方法一、遍历
     */
    public static int count = 0;
    public int getNodeCounts1(BTNode root){
        if(root == null){
            return 0;
        }
        count++;
        getNodeCounts1(root.left);
        getNodeCounts1(root.right);
        return count;
    }
    /**
     * 得到二叉树的结点个数
     * 方法二、转为子问题
     */
    public int getCounts2(BTNode root) {
        if(root == null){
            return 0;
        }
        return getCounts2(root.left) + getCounts2(root.right) + 1;
    }
}
